package demo1;
import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */

//链表的中间节点
public class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //删除链表中的所有val
    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            head = head.next;
        }
        if(head == null){
            return null;
        }
        ListNode pcur = head.next;
        ListNode prev = head;
        while(pcur != null){
            if(pcur.val == val){
                prev.next = pcur.next;
            }else{
                pcur = pcur.next;
                prev = prev.next;
            }
        }
        return head;
    }

    //回文链表
    public boolean chkPalindrome(ListNode head) {
        // write code here
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode pcur = slow.next;
        ListNode prev = slow;
        while(pcur != null){
            ListNode apcur = pcur;
            pcur = pcur.next;
            apcur.next = prev;
            prev = apcur;
        }
        slow = prev;
        pcur = head;
        while(pcur!=slow){
            if(pcur.next == slow){
                return true;
            }
            pcur = pcur.next;
            slow = slow.next;
        }
        if(pcur == slow){
            return true;
        }else {
            return false;
        }
    }

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode pcur = head;
        while(list1 != null && list2 !=null){
            if(list1.val >= list2.val){
                pcur.next = list2;
                pcur = pcur.next;
                list2 = list2.next;
            }else{
                pcur.next = list1;
                pcur = pcur.next;
                list1 = list1.next;
            }
        }
        pcur.next = list1 == null ? list2 : list1;
        return head.next;


//        ListNode head = null;
//        ListNode pcur = head;
//        while(list1 != null && list2 !=null){
//            if(list1.val >= list2.val){
//                if(pcur==null){
//                    pcur = list2;
//                }
//                pcur.next = list2;
//                pcur = pcur.next;
//                list2 = list2.next;
//            }else{
//                if(pcur==null){
//                    pcur = list1;
//                }
//                pcur.next = list1;
//                pcur = pcur.next;
//                list1 = list1.next;
//            }
//        }
//        if(list1 == null){
//            while(list2 != null){
//                if(pcur==null){
//                    pcur = list2;
//                }
//                pcur.next = list2;
//                pcur = pcur.next;
//                list2 = list2.next;
//            }
//        }
//        if(list2 == null){
//            while(list1 != null){
//                if(pcur==null){
//                    pcur = list1;
//                }
//                pcur.next = list1;
//                pcur = pcur.next;
//                list1 = list1.next;
//            }
//        }
//        return head;
    }
}
